package com.xyhuo.leetcode.january;

import com.xyhuo.leetcode.common.TreeNode;

/**
 * 将有序数组转换成二叉搜索树
 * https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
 *
 * @time 2024/1/9
 */
public class SortedArrayToBST {

//    public static void main(String[] args) {
//        SortedArrayToBST satbst = new SortedArrayToBST();
//        int[] nums = {-10, -3, 0, 5, 9};
//        TreeNode treeNode = satbst.sortedArrayToBST(nums);
//        System.out.println(treeNode);
//    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return search(nums, 0, nums.length - 1);
    }

    private TreeNode search(int[] nums, int left, int right) {
        if (left > right || left < 0 || right >= nums.length) {
            return null;
        }
        if (left == right) {
            return new TreeNode(nums[left]);
        }
        int middle = (right - left) / 2;
        TreeNode root = new TreeNode(nums[left + middle]);
        root.left = search(nums, left, left + middle - 1);
        root.right = search(nums, left + middle + 1, right);
        return root;
    }
}
